import java.util.LinkedList;
import java.util.List;

public class Solution54 {
    List<Integer> result;
    boolean[][] mark;
    final int[] direcX=new int[]{1,0,-1,0};
    final int[] direcY=new int[]{0,1,0,-1};

    public void travel(int tmpX,int tmpY,int[][] matrix,int lastDirec){
        mark[tmpY][tmpX]=true;
        result.add(matrix[tmpY][tmpX]);
        for (int i = 0; i < 4; i++) {
            int tmpDirec=(lastDirec+i)%4;
            int newX=tmpX+direcX[tmpDirec];
            int newY=tmpY+direcY[tmpDirec];
            if((0<=newX&&newX< matrix[0].length)&&(0<=newY&&newY< matrix.length)&&(mark[newY][newX]==false)){
                travel(newX,newY,matrix,tmpDirec);
                return;
            }
        }
        return;
    }



    public List<Integer> spiralOrder(int[][] matrix) {
        mark=new boolean[matrix.length][matrix[0].length];
        result=new LinkedList<>();
        travel(0,0,matrix,0);
        return result;
    }
}
